void HeapSort ( SqList *L ) 
{
	BuildMaxHeap(L) ;                // 建大顶堆
	for ( i=L->length; i>1; --i ) 
	{
  		L->elem[1]←→L->elem[i]; //将堆顶元素和当前未经排序子序列
                                                 // L.elem[1..i]中最后一个元素交换
   		MaxHeapify(L, 1, i-1);         //调整L.elem[1..i-1]使其成为大顶堆
	}	
} // HeapSort

void BuildMaxHeap(SqList *L) 
/* L.length/2 +1 到L.length之间均为叶结点，因此，L.length/2为第一个非叶子结点。*/
{
	for ( i=L->length/2; i>0; --i )
		MaxHeapify( L, i, L->length ); // 建大顶堆
}

void MaxHeapify (SqList *L, int s, int m)
{//已知L->elem[s..m]中除 L->elem[s]之外均满足大顶堆的特征，
 //本函数自顶向下调整 L->elem[s],使L->elem[s..m]成为大顶堆。
	rc = L->elem[s];    // 暂存 L->elem[s] 
	for ( j=2*s; j<=m; j*=2 )
	{ // j 初值指向左孩子
						/*自上而下的筛选过程;*/
		if ( j<m && L->elem[j]<L->elem[j+1] )  ++j;     
	// 左/右“孩子”之间先进行相互比较
	// 令 j 指示较大的关键字所在位置
		if ( rc >= L->elem[j] )  break; 
	// 再作“根”和“孩子”之间比较。
	// 若“>=”成立，则说明已找到 rc 的插入位置 s,
	// 不需继续向下调整
		L->elem[s] = L->elem[j];   s = j;    
	// 否则关键字上移，仍需继续向下调整
	}
	L->elem[s] = rc;//将调整前的堆顶插入到s位置
} // HeapAdjust